package com.leetcode.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Dennis Li
 * @date 2020/7/28 17:09
 */
public class IsBipartite_785 {

    public boolean isBipartite(int[][] graph) {
        if (graph == null || graph.length == 0) return true;
        boolean[] A = new boolean[graph.length];
        boolean[] B = new boolean[graph.length];
        Queue<Integer> queue = new LinkedList<>();
        // 需要遍历整个图，防止有一些结点不连通
        for (int i = 0; i < graph.length; i++) {
            // 如果已经出现过，那么就跳过
            if (A[i] || B[i]) continue;
            queue.offer(i);
            // 没有在A出现那么就将A置为true
            if (!A[i]) A[i] = true;
            // 否则在B中置为true
            else B[i] = true;
            while (!queue.isEmpty()) {
                int now = queue.poll();
                for (int v : graph[now]) {
                    // 还没有出现过的点
                    if (!A[v] && !B[v]) queue.offer(v);
                    // 必须要放在另一个集合中
                    if (A[now]) B[v] = true;
                    else A[v] = true;
                }
            }
        }
        for (int i = 0; i < graph.length; i++) {
            // 如果在一个集合中出现了两次，那么返回false
            if (A[i] == B[i]) return false;
        }
        return true;
    }

}
